#include "randnum.h"
#include <windows.h>
#include <sortthread.h>
#include <iostream>
using namespace std;

void SortThread::binInsertSort(SortObject * pvector)
{
    int i, j, left, mid, right;
    sortTle = 0;
    sortMov = 0;
    sortCmp = 0;
    pvector->n = this->size;
    RecordNode temp;
    RecordNode *data = pvector->record;
    for (i = 1; i < pvector->n; i++)
    {
        sortTle++;
        temp = data[i];
        this->sendt(sortTle,sortMov,sortCmp);
        left = 0;  right = i - 1;           /* 置已排序区间的下、上界初值 */
        while (left <= right)
        {
            mid = (left + right) / 2;       /* mid指向已排序区间的中间位置 */
            if (temp.key < data[mid].key)
            {
                sortCmp++;
                right = mid - 1;            /* 插入元素应在左子区间 */
                this->senda(right,mid);
                this->sendt(sortTle,sortMov,sortCmp);
            }
            else
            {
                sortCmp++;
                left = mid + 1;             /* 插入元素应在右子区间 */
                this->senda(left,mid);
                this->sendt(sortTle,sortMov,sortCmp);
            }
        }
        for (j = i - 1; j >= left; j--)
        {
            data[j + 1] = data[j];          /* 将排序码大于ki的记录后移 */
            for(int ii = 0; ii < pvector->n; ii++)
            {
                this->sendArray[ii] = data[ii].key;
            }
        }
        this->senda(j,left);
        if (left != i)
        {
            sortMov++;
            data[left] = temp;
            //this->sendArray[i] = data[i].key;
            this->senda(i,left);
            this->sendt(sortTle,sortMov,sortCmp);
        }
        for(int ii = 0; ii < pvector->n; ii++)
        {
            this->sendArray[ii] = data[ii].key;
        }
    }
    for(int i = 0; i < size; i++)
    {
        senda(i,-10);
    }
    this->sendt(sortTle,sortMov,sortCmp);
}
